package company;

import java.util.*;

/**
 * 127 单词接龙 bfs+dfs 官方
 * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
 * <p>
 * 每对相邻的单词之间仅有单个字母不同。
 * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * 解释：存在 2 种最短的转换序列：
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：[]
 * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
 */
public class FindLaddersFive127 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String beginWords = sc.nextLine();
        String endWords = sc.nextLine();
        String[] split = sc.nextLine().split(",");
        List<String> wordIdList = new ArrayList<>(Arrays.asList(split));
        List<List<String>> ladders = findLadders(beginWords, endWords, wordIdList);
        for (List<String> list : ladders) {
            for (String word : list) {
                System.out.print(word + "->");
            }
            System.out.println();
        }
    }

    public static List<List<String>> findLadders(String beginWordCode, String endWordCode, List<String> wordCodes) {
        List<List<String>> wordCodePaths = new ArrayList<>();

        // 剪枝：开始单词 = 结束单词
        if (beginWordCode.contentEquals(endWordCode)) {
            // 查看结束单词是否在列表中
            if (wordCodes.contains(endWordCode)) {
                wordCodePaths.add(Collections.singletonList(beginWordCode));
                return wordCodePaths;
            }
        }

        // 剪枝：单词长度是否为1，表示直接转换
        if (beginWordCode.length() == 1) {
            if (wordCodes.contains(endWordCode)) {
                wordCodePaths.add(Arrays.asList(beginWordCode, endWordCode));
                return wordCodePaths;
            }
        }

        // 使用虚拟节点构建图
        WordGraphLinker wordGraphLinker = new WordGraphLinker();
        Word endWord = null;
        for (String wordCode : wordCodes) {
            // 把单词加入图中，并返回单词的节点对象
            Word word = wordGraphLinker.add(wordCode);
            // 查找结束单词是否在单词列表中
            if (endWord == null && wordCode.equals(endWordCode)) {
                endWord = word;
            }
        }
        if (endWord == null) {
            return wordCodePaths;
        }

        // 反方向查找的起始步数为2，它的增长序列将为：2,4,6,...
        // 作用：与正方向交叉增长步数
        endWord.step = 2;
        // 0表示未遍历，正数表示正方向遍历，负数表示反方向遍历，数值表示步长
        // 作用：两节点的标志值相加值为0时，表示找到最短路径
        endWord.flag = -2;

        // 因为开始单词不再单词列表，也需要加入到图中，并返回节点对象
        Word beginWord = wordGraphLinker.add(beginWordCode);
        // 正方向查找的起始步数为1，它的增加序列将为：1,3,5,...
        // 作用：与反方向交叉增长步数
        beginWord.step = 1;
        // 0表示未遍历，正数表示正方向遍历，负数表示反方向遍历，数值表示步长
        // 作用：两节点的标志值相加值为0时，表示找到最短路径
        beginWord.flag = 2;

        // 设置最短路径的长度为最大值
        int minStep = Integer.MAX_VALUE;

        // 使用双向广度优先遍历
        ArrayDeque<Word> queueWords = new ArrayDeque<>();
        // 开始和结束节点先后加入队列，表示先从正方向开始遍历，再从反方向开始遍历
        queueWords.add(beginWord);
        queueWords.add(endWord);
        while (!queueWords.isEmpty()) {
            // 从队列中取出队头节点
            Word word = queueWords.poll();
            // 当节点的步数超出了最短路径的长度时，则队列
            if (word.step > minStep) {
                break;
            }
            for (Word neighbor : word.neighbors) {
                // step值为0时，表示该节点未遍历
                if (neighbor.step == 0) {
                    // 剪枝：排除邻接点数量为1的节点
                    if (neighbor.neighbors.size() <= 1) {
                        continue;
                    }
                    // 增加步数
                    // 正方向查找的起始步数为1，它的增加序列将为：1,3,5,...
                    // 反方向查找的起始步数为2，它的增长序列将为：2,4,6,...
                    // 作用：正方向与反方向交叉增长步数
                    neighbor.step = word.step + 2;
                    // 继承遍历方向
                    neighbor.flag = word.flag;
                    queueWords.add(neighbor);
                }
                // 当两节点的方向值相加为0时，表示找到了最短路径
                else if (word.flag + neighbor.flag == 0) {
                    // 记录最短路径的长度
                    minStep = word.step;
                    if (word.flag > 0) {
                        word.makeMinPath(word.step); // 标记正方向的所有节点为最短路径上的节点
                        word.makeMinPath(word.step + 2); // 标记负方向的所有节点为最短路径上的节点
                    } else {
                        word.makeMinPath(neighbor.step); // 标记正方向的所有节点为最短路径上的节点
                        word.makeMinPath(neighbor.step + 2); // 标记负方向的所有节点为最短路径上的节点
                    }
                }
            }
        }

        if (minStep < Integer.MAX_VALUE) {
            beginWord.genMinCodePaths(wordCodePaths, new ArrayList<>());
        }
        return wordCodePaths;
    }
}

class WordGraphLinker {
    public final Map<String, Word> value = new HashMap<>();

    public Word add(String wordCode) {
        // 构建真实节点
        Word word = new Word(wordCode, true);
        char[] chars = wordCode.toCharArray();
        for (int i = 0; i < wordCode.length(); i++) {
            char c = chars[i];
            chars[i] = '*';
            // 构建虚拟节点
            String virtualWordCode = new String(chars);
            Word virtualWord = this.value.computeIfAbsent(virtualWordCode, k -> new Word(virtualWordCode, false));
            // 真实节点与虚拟节点关联
            virtualWord.neighbors.add(word);
            word.neighbors.add(virtualWord);
            chars[i] = c;
        }
        return word;
    }
}

class Word {
    public int step = 0; // 遍历步数，0表示未遍历，1表示开始节点，2表示结束节点,奇数表示正方向遍历，偶数表示反方向遍历
    public int flag = 0; // 0表示未遍历，正数表示正方向遍历，负数表示负方向遍历
    public final String code;
    public int minPathStep = 0; // 在最短路径上的步数，0表示不在最短路径上
    public final boolean real; // true表示真实节点，false表示虚拟节点
    // 邻接点列表
    public final List<Word> neighbors = new ArrayList<>();

    public Word(String code, boolean real) {
        this.code = code;
        this.real = real;
    }

    /**
     * 标记节点和它的来源节点为最短路径上的节点
     */
    public void makeMinPath(int minPathStep) {
        // 大于0表示已经在最短路径上
        if (this.minPathStep > 0) {
            return;
        }
        // 记录节点在最短路径上的步数
        this.minPathStep = minPathStep;
        // 1是开始节点，2是结束节点，表示已经到源头
        if (step <= 2) {
            return;
        }
        // 找出来源邻接点
        int step = this.step - 2;
        for (Word neighbor : neighbors) {
            if (neighbor.step == step) {
                // 递归标记来源邻接点为最短路径上的节点
                neighbor.makeMinPath(minPathStep - this.flag);
            }
        }
    }

    /**
     * 生成所有的最短路径
     */
    public void genMinCodePaths(List<List<String>> minCodePaths, List<String> minCodePath) {
        // 如果是真实节点，则写入最短路径中
        if (this.real) {
            minCodePath.add(this.code);
            // 当找到结束节点时，则退出递归
            if (this.step == 2) {
                minCodePaths.add(minCodePath); // 遇到结束节点，写入结果集
                return;
            }
        }
        // 寻找下一个最短路径上的邻接点
        int pathStep = this.minPathStep + 2;
        for (Word neighbor : neighbors) {
            if (neighbor.minPathStep == pathStep) {
                // 递归把邻接点加入最短路径
                neighbor.genMinCodePaths(minCodePaths, new ArrayList<>(minCodePath));
            }
        }
    }
}
